package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:组合
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
 *
 * 示例1：
 * 输入：n = 4, k = 2
 * 输出：
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 *
 * author: Mr.Du
 * Date: 2022/11/11
 * Time: 10:20
 */
public class Combine {
    
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();
    
    public static void main(String[] args) {
        Combine c = new Combine();
        List<List<Integer>> combine = c.combine(4, 2);
        System.out.println(combine);
    }
    
    public List<List<Integer>> combine(int n, int k) {
        dd(n,k,1);
        return res;
    }
    
    /**
     * 思路：
     *      退出条件：k == list.size()
     *      做选择：就是直接加入
     *      回溯：下标开始加1
     *      回退：移除最后一个元素
     * @param n
     * @param k
     * @param start
     */
    public void dd(int n, int k,int start){
        if(list.size() == k){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = start;i <= n;i++){
            list.add(i);
            dd(n,k,i+1);
            list.removeLast();
        }
    }
}
